package mlProject.classifier;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class DecisionTreeCreater {
	
	public DTNode startNode;
	public int iteratorCnt = 1;
	public int nodeCnt = 0;
	
	public DecisionTreeCreater(){
		startNode = new DTNode();
	}
	
	public void generateTree(List<DataModel> data,List<String> attrList, DTNode node){
		//给每个节点赋上名字
		node.index = String.valueOf(nodeCnt++);
		
		System.out.println("- start generateTree for node:<"+(node.index)+">...");
		System.out.println("\tdataSize is:"+data.size());
		System.out.println("\tattrList is:"+attrList);
		if(isOneType(data) || attrList.size() == 0){
			node.isLeaf = true;
			String label = getMostLabels(data);  //这一步还可以优化
			node.value = label;
			
			System.out.println("\t-fount one leaf, label is <"+label+">,parent is node:"+node.index);
			return;
		}
		
		Object[] splittingCriterion = attributeSelection(data, attrList);
		String selectedAttr = (String) splittingCriterion[0];
		
		
		node.attr = selectedAttr;      //先给当前节点附上attr的值
		attrList.remove(selectedAttr); //在attrList中删除选定属性
		
		//仅仅使用二分的方法
		if(isNumericAttr(selectedAttr)){
			Double spliter = (Double) splittingCriterion[1];
			List<List<DataModel>> dataGroups = divideDataByAttr(data, selectedAttr, spliter);
			
			System.out.println("- divide data to "+dataGroups.size()+" Groups by N_attr");
			
			//加入左子树
			DTNode tmpNode = new DTNode();
			tmpNode.parent = node;
			DTEdge tmpEdge = new DTEdge(node, tmpNode);
			tmpEdge.operator = '<';
			tmpEdge.value = String.valueOf(spliter);
			node.edges.add(tmpEdge);
			System.out.println("- add Left Edge \n\toperator:"+tmpEdge.operator+"\tvalue:"+tmpEdge.value);
			generateTree(dataGroups.get(0), attrList, tmpNode);
			
			//加入右子树
			DTNode tmpNoder = new DTNode();
			tmpNoder.parent = node;
			DTEdge tmpEdger = new DTEdge(node, tmpNoder);
			tmpEdger.operator = '>';
			tmpEdger.value = String.valueOf(spliter);
			node.edges.add(tmpEdger);
			System.out.println("- add Right Edge \n\toperator:"+tmpEdger.operator+"\tvalue:"+tmpEdger.value);
			generateTree(dataGroups.get(1), attrList, tmpNoder);
			
		}else{
			
			Map<String, List<DataModel>> dataGroups = divideDataByAttr(data, selectedAttr);
			System.out.println("- divide data to "+dataGroups.size()+" Groups by attr");
			
			for(String key:dataGroups.keySet()){
				DTNode tmpNode = new DTNode();
				tmpNode.parent = node;
				DTEdge tmpEdge = new DTEdge(node, tmpNode);
				tmpEdge.operator = '=';
				tmpEdge.value = key;
				
				//将新的边加入node中
				node.edges.add(tmpEdge);
				System.out.println("- add one Edge \n\toperator:"+tmpEdge.operator+"\tvalue:"+tmpEdge.value);
				//递归调用
				generateTree(dataGroups.get(key),attrList,tmpNode);
			}
		}
		
	}
	
	/**
	 * 
	 * @param data
	 * @param attrList
	 * @return object[0] 表示选中的属性  object[1] 表示spliter
	 */
	public Object[] attributeSelection(List<DataModel> data,List<String> attrList){
//		double infoD =  info(data);
		System.out.println("- select attr in attrList...");
		double minInfo = Double.MAX_VALUE;
		Double spliter = null;  // spliter == null表示选中的attr是离散值
		String selectedAttr = null;
		
		for(int i = 0; i < attrList.size();i++){
			String tmpAttr = attrList.get(i);
			if(isNumericAttr(tmpAttr)){
				double[] tmpInfoA = infoA(data,tmpAttr);
				System.out.println("\tinfoA("+tmpAttr+")="+tmpInfoA[1]);
				if(tmpInfoA[1] < minInfo){
					spliter = tmpInfoA[0];
					minInfo = tmpInfoA[1];
					selectedAttr = tmpAttr;
				}
			}else{
				Map<String,List<DataModel>> dataGroups = divideDataByAttr(data, tmpAttr);
				double tmpInfoA = infoA(dataGroups,data.size());
				System.out.println("\tinfoA("+tmpAttr+")="+tmpInfoA);
				if(tmpInfoA < minInfo){
					spliter = null;
					minInfo = tmpInfoA;
					selectedAttr = tmpAttr;
				}
			}
		}
		System.out.println("- select attr<"+selectedAttr+">");
		return new Object[]{selectedAttr,spliter};
	}
	
	public boolean isNumericAttr(String attr){
		if(attr.startsWith("N_")){
			return true;
		}
		return false;
	}
	
	/**
	 * 
	 * @param data
	 * @param attr
	 * @return ret[0] 表示分界点，ret[1] 表示infoA的值
	 */
	public double[] infoA(List<DataModel> data,final String attr){
		Collections.sort(data, new Comparator<DataModel>() {
			@Override
			public int compare(DataModel o1, DataModel o2) {
				double v1 = (double) (o1.attrs.get(attr));
				double v2 = (double) (o2.attrs.get(attr));
				if(v1 > v2)
					return 1;
				if(v1 < v2)
					return -1;
				return 0;
			}
		});
		
//		data.sort(new Comparator<DataModel>() {
//			@Override
//			public int compare(DataModel o1, DataModel o2) {
//				double v1 = Double.valueOf(o1.attrs.get(attr));
//				double v2 = Double.valueOf(o2.attrs.get(attr));
//				if(v1 > v2)
//					return 1;
//				if(v1 < v2)
//					return -1;
//				return 0;
//			}
//		});
		
		List<DataModel> group1 = new ArrayList<DataModel>();
		List<DataModel> group2 = new ArrayList<DataModel>();
		group2.addAll(data);
		
		Map<String,Integer> map1 = new HashMap<String, Integer>();
		Map<String,Integer> map2 = new HashMap<String, Integer>();
		
		//为map2进行更新
		for(int i = 0 ;i < group2.size() ;i++){
			DataModel tmpData = group2.get(i);
			updateLabelMap(map2, tmpData, '+');
		}
		
		
		
		double minInfo = Double.MAX_VALUE;
		double spliter = 0;
		for(int i = 0; i < data.size()-1 ;i++){
			group1.add(data.get(i));
			updateLabelMap(map1,data.get(i),'+');
			
			group2.remove(0);   //注意这个地方删除的是头上的元素
			updateLabelMap(map2,data.get(i),'-');
			
			double v1 = (double) (data.get(i).attrs.get(attr));
			double v2 = (double) (data.get(i+1).attrs.get(attr));
			
			//优化计算info的方法，防止大量的重复计算
			double tmpinfo = 1.0*group1.size()/data.size()*simpleInfo(map1,group1.size())+
					1.0*group2.size()/data.size()*simpleInfo(map2,group2.size());
//			double tmpinfo = 1.0*group1.size()/data.size()*info(group1)+
//					1.0*group2.size()/data.size()*info(group2);
		
			if(minInfo > tmpinfo){
				minInfo = tmpinfo;
				spliter = (v1+v2)/2;
			}
		}
		double[] ret = new double[2];
		ret[0] = spliter;
		ret[1] = minInfo;
		return ret;
	}
	
	public void updateLabelMap(Map<String,Integer> labelMap,DataModel data,char operator){
		String label = data.label;
		if(!labelMap.containsKey(label)){
			labelMap.put(label, 1);
		}else{
			if(operator == '+'){
				labelMap.put(label, labelMap.get(label)+1);
			}
			else if(operator == '-'){
				int tmpCnt = labelMap.get(label);
				labelMap.put(label, tmpCnt-1);
				if(tmpCnt == 1){
					labelMap.remove(label);
				}
			}
		}
	}
	
	//计算属性值为离散的infoA方法
	public double infoA(Map<String,List<DataModel>> dataGroup,int size){
		double infoA = 0.0;
		for(String key:dataGroup.keySet()){
//		for(int i = 0;i< dataGroup.size();i++){
			List<DataModel> tmpData = dataGroup.get(key);
			infoA += ((1.0*tmpData.size()/size)*info(tmpData));
		}
		return infoA;
	}
	
	public Map<String,List<DataModel>> divideDataByAttr(List<DataModel> data,String attr){
//		List<List<DataModel>> dataGroup = new ArrayList<List<DataModel>>();
		Map<String,List<DataModel>> dataMaps = new HashMap<String, List<DataModel>>();
		
		for(int i = 0 ;i < data.size();i++){
			DataModel tmpData = data.get(i);
			if(!dataMaps.containsKey(tmpData.attrs.get(attr))){
				List<DataModel> tmpGroup = new ArrayList<DataModel>();
				tmpGroup.add(tmpData);
				dataMaps.put((String) tmpData.attrs.get(attr), tmpGroup);
			}else{
				List<DataModel> tmpGroup = dataMaps.get(tmpData.attrs.get(attr));
				tmpGroup.add(tmpData);
				dataMaps.put((String) tmpData.attrs.get(attr), tmpGroup);
			}
		}
		
//		for(List<DataModel> tmpList:dataMaps.values()){
//			dataGroup.add(tmpList);
//		}
//		return dataGroup;
		return dataMaps;
	}
	
	public List<List<DataModel>> divideDataByAttr(List<DataModel> data,String attr,double spliter){
		List<List<DataModel>> dataGroup = new ArrayList<List<DataModel>>();
		List<DataModel> groupl = new ArrayList<DataModel>();
		List<DataModel> groupr = new ArrayList<DataModel>();
		
		for(int i = 0; i < data.size();i++){
			DataModel tmpData = data.get(i);
			if((double)(tmpData.attrs.get(attr)) <= spliter){
				groupl.add(tmpData);
			}else{
				groupr.add(tmpData);
			}
		}
		
		dataGroup.add(groupl);
		dataGroup.add(groupr);
		return dataGroup;
	}
	
	
	public double info(List<DataModel> data){
		int size = data.size();
		
		Map<String,Integer> cntMap = new HashMap<String,Integer>();
		for(int i = 0 ;i < data.size() ;i++){
			String label = data.get(i).label;
			if(!cntMap.containsKey(label)){
				cntMap.put(label, 1);
			}else{
				cntMap.put(label, cntMap.get(label)+1);
			}
		}
		
		double info = 0.0;
		for(String key:cntMap.keySet()){
			int tmpCnt = cntMap.get(key);
			info -= (1.0*tmpCnt/size*log2(1.0*tmpCnt/size));  //度量函数
		}
		
		return info;
		
	}
	
	public double simpleInfo(Map<String,Integer> labelMap,int size){
		double info = 0.0;
		for(String key:labelMap.keySet()){
			int tmpCnt = labelMap.get(key);
			info -= (1.0*tmpCnt/size*log2(1.0*tmpCnt/size));  //度量函数
		}
		
		return info;
	}
	
	public double log2(double n){
		return Math.log(n)/Math.log(2.0);
	}
	
	//返回D中的多数类
	public String getMostLabels(List<DataModel> data){
		Map<String,Integer> cntMap = new HashMap<String,Integer>();
		for(int i = 0;i< data.size();i++){
			String label = data.get(i).label;
			if(!cntMap.containsKey(label)){
				cntMap.put(label, 1);
			}else{
				cntMap.put(label, cntMap.get(label)+1);
			}
		}
		int maxv = 0;
		String label = null;
		for(String key: cntMap.keySet()){
			int tmpCnt = cntMap.get(key);
			if(maxv < tmpCnt){
				maxv = tmpCnt;
				label = key;
			}
		}
		
		return label;
	}
	
	public boolean isOneType(List<DataModel> data){
		String value = null;
		if(data.size()>1){
			value = data.get(0).label;
		}
		else{
			return true;
		}
		
		for(int i = 0;i<data.size();i++){
			if(!value.equals(data.get(i).label)){
				return false;
			}
		}
		return true;
	}
	
	public void printDTree(DTNode startNode){
		
	}
}
































